#include <iostream>
#include <algorithm> // 算法库
#include <list>
#include <vector>
// #include<bits/stdc++.h>//万能头文件
using namespace std;

template <typename Container, typename T>
void Remove(Container &v, const T &value)
{
    for (auto ite = v.begin(); ite != v.end();)
    {
        if (*ite == value)
            ite = v.erase(ite);
        else
            ite++;
    }
}

template <typename Iterator>
void RandomShuffle(Iterator start, Iterator end)
{
    if (start == end)
        return;
    for (auto i = start + 1; i != end; i++)
    {
        auto j = start + std::rand() % (i - start + 1);
        if (i != j)
            swap(*i, *j);
    }
}

int main()
{
    // 所有C++代码都包在std里面
    // 非变动性算法-------------------------------------------------------------------------------------------
    // vector<int> v = {1, 2, 2, 3, 3, 4, 5};
    // for_each(v.begin(), v.end(), [](int a)  // 对每个元素执行操作
    //          { cout << a << " "; });
    // cout << endl;

    // cout << count(v.begin(), v.end(), 2) << endl;  // 返回元素个数
    // cout << count_if(v.begin(), v.end(), [](int a)   // 返回满足某一条件的元素个数
    //                  { return a % 2 != 0; })
    //      << endl;
    // cout<<*min_element(v.begin(),v.end())<<endl;  // 返回最小值元素
    // cout<<*max_element(v.begin(),v.end())<<endl;   // 返回最大值元素
    // auto ite = find_if(v.begin(), v.end(), [](int a)  // 搜索满足某个条件的第一个元素
    //                 { return a % 2 != 0 && a > 4; });
    // // 找不到就返回end迭代器
    // if (ite != v.end())
    // {
    //     cout << *ite << endl;
    // }

    // search_n 查找n个连续的值
    //  auto ite= search_n(v.begin(),v.end(),3,3);  // 搜索具有某特性的 第一段 n个 连续元素
    //  cout<<*ite<<endl;
    // vector<int> v = {1, 2, 2, 3, 3, 4, 5};
    // vector<int> v2 = {2, 3, 3, 4, 5};
    // 在前一个区间找后一个区间  返回找到的在第一个区间的迭代器
    // auto ite = search(v.begin(), v.end(), v2.begin(), v2.end());  // 搜索某个子区间第一次出现的位置

    // auto ite=find_end(v.begin(),v.end(),v2.begin(),v2.end());  // 搜索某个子区间最后一次出现的位置
    // cout << *ite << endl;

    // 在第一个区间中找第二个区间的第一次出现的元素
    // auto ite = find_first_of(v.begin(), v.end(), v2.begin(), v2.end());
    // cout << *ite << endl;

    // 找连续两个相等的元素
    //  auto ite=adjacent_find(v.begin(),v.end());
    //  cout<<*ite<<endl;

    // cout<<equal(v.begin(),v.end(),v2.begin(),v2.end())<<endl;  // 判断两区间是否相等

    // 返回两个序列的各组对应元素中，第一对不相等的元素
    // vector<int> v = {3, 4, 5};
    // vector<int> v2 = {2, 3, 5};
    // string s1="hello";
    // string s2="hollo";
    // auto pair = mismatch(s1.begin(), s1.end(), s2.begin(), s2.end());
    // cout << *pair.first << " " << *pair.second << endl;  // 输出 e o

    // 变动性算法---------------------------------------------------------------------------
    // 变动性算法一定要留足空间
    vector<int> v = {1, 2, 3, 3, 4, 5};
    for_each(v.begin(), v.end(), [](int &a){ a++; cout<<a<<" "; }); // 传引用 
    // list<int> l;
    // l.resize(v.size());  // 先扩容

    // // copy_backward(v.begin(), v.end(), l.end());
    // transform(v.begin(), v.end(), l.begin(), [](int a)
    //           { return a * 2; });

    // vector<int> v2;
    // v2.resize(v.size() + l.size());
    // merge(v.begin(), v.end(), l.begin(), l.end(), v2.begin());

    // swap_ranges(v.begin(),v.end(),l.begin());

    // 数组用fill  list用fill_n
    // fill(v.begin(), v.end(), 0);
    // fill_n(l.begin(), 3, 0);
    // int a = 0;

    // generate(v.begin(), v.end(), [&a]()
    //          { return ++a; });

    // vector<int> v = {1, 1, 2, 3, 4, 5};
    // vector<int> v2;
    // v2.resize(v.size());
    // replace(v.begin(),v.end(),1,99);
    // replace_copy(v.begin(),v.end(),v2.begin(),1,99);
    // replace_if(v.begin(), v.end(), [](int a)
    //            { return a < 4; }, 99);
    // for_each(v.begin(), v.end(), [](int &a)
    //          { cout << a << " "; });
    // replace_copy_if(v.begin(), v.end(), v2.begin(), [](int a)
    //                 { return a < 4; }, 99);
    // for_each(v2.begin(), v2.end(), [](int &a)
    //          {cout<<a<<" "; });
    // cout << endl;

    // vector<int> v = {1, 2, 3, 4, 5};
    //  reverse(v.begin(),v.end());
    /// Remove(v,3);

    // forward_list<int>v={1,2,3,4,5};
    // v.reverse();

    // rotate(v.begin(),v.begin()+2,v.end());

    // prev_permutation(v.begin(),v.end());

    // srand(time(nullptr));
    // random_shuffle(v.begin(), v.end());

    // 不稳定 partition
    //   稳定
    //  stable_partition(v.begin(),v.end(),[](int a){return a%2==0;});

    // for_each(v.begin(), v.end(), [](int a)
    //          { cout << a << " "; });
    // cout << endl;

    // vector<int> v = {5, 1, 4, 2, 3};
    //  size<16 插入排序
    //   > 16 递归深度归0  堆排序
    //         不为0   快速排序
    //  sort(v.begin(), v.end(), std::greater<int>());

    // size <15   插入排序
    //  >15    分组  插入   归并
    // stable_sort(v.begin(), v.end(), std::greater<int>());

    // partial_sort(v.begin(),v.begin()+2,v.end());
    // 只排第n个元素
    // nth_element(v.begin(),v.begin(),v.end());
    // make_heap(v.begin(),v.end());
    //  make_heap(v.begin(),v.end(),std::greater<int>());
    //  v.push_back(12);
    //  push_heap(v.begin(),v.end());//塞入一个新元素以后，再构建堆
    //  //pop_heap(v.begin(),v.end());
    //  sort_heap(v.begin(),v.end());
    //  for_each(v.begin(), v.end(), [](int &a)
    //           { cout << a << " "; });
    //  cout << endl;

    // vector<int> v = {1, 2,2,2, 3, 4, 5};
    // vector<int> v2 = {1, 2};
    // cout << binary_search(v.begin(), v.end(), 2) << endl;
    // cout<<includes(v.begin(),v.end(),v2.begin(),v2.end())<<endl;
    // 大于等于
    // cout << *lower_bound(v.begin(), v.end(), 2) << endl;
    // //大于
    // cout << *upper_bound(v.begin(), v.end(), 2) << endl;

    // auto pair = equal_range(v.begin(), v.end(), 2);
    // // cout << distance(v.begin(), pair.first) << endl;
    // // cout << distance(v.begin(), pair.second) << endl;
    // cout<<distance(pair.first,pair.second)<<endl;

    // vector<int> v1 = {1, 2, 3,1,2,3};
    // vector<int> v2 = {2, 3, 4};
    // vector<int> result;
    // result.resize(v1.size() + v2.size());
    // set_union(v1.begin(), v1.end(), v2.begin(), v2.end(), result.begin());
    // set_intersection(v1.begin(),v1.end(),v2.begin(),v2.end(),result.begin());
    // set_difference(v1.begin(),v1.end(),v2.begin(),v2.end(),result.begin());
    // set_symmetric_difference(v1.begin(),v1.end(),v2.begin(),v2.end(),result.begin());
    // inplace_merge(v1.begin(),v1.begin()+3,v1.end());
    // for_each(v1.begin(), v1.end(), [](int &a)
    //          { cout << a << " "; });

    return 0;
}
